package arithmetic;

import java.util.Scanner;

public class TestHW16 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        try {
            String[] str = in.nextLine().split(" ");
            int money = Integer.parseInt(str[0]);
            int num = Integer.parseInt(str[1]);
            if (money < 0 || money >= 32000)return;
            if (num <= 0 || num >= 60)return;
            // if(test(in, num)==null)return;
            int[][] ins = test(in, num, money);
            if (ins == null)return;
            int len = test3(ins.length, 1);
            // System.out.println(len + "::");
            int[][][] ins2 = new int[len][ins.length][4];
            ins2 = test212(ins2, 0, ins, 0);
            test4(ins2, money);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    //获取vpq

    public static int[][] test(Scanner in, int num, int money) {
        int[][] ins = new int[num][4];
        int b = 0;
        for (int i = 0; i < num; i++) {
            String str1 = in.nextLine();
            String[] strs = str1.split(" ");
            if (strs.length != 3) return null;
            b++;
            int v = Integer.parseInt(strs[0]);
            if(v>money)continue;
            int p = Integer.parseInt(strs[1]);
            int q = Integer.parseInt(strs[2]);
            if(q>0 && q==b)continue;
            if (v < 0 || v > 10000 || p < 1 || p > 5 || q < 0) return null;
            ins[i][0] = v;
            ins[i][1] = p;
            ins[i][2] = q;
            ins[i][3] = i + 1; //编号
        }
        return ins;
    }


    //所有可能的组合形式
    public static int[][][] test212(int[][][]ins2, int ins2Index, int[][] ins,
                                    int index) {
        if (ins.length == index) {
            return ins2;
        }
        int[] ele = ins[index];
        ins2[ins2Index][0] = ele;
        int len = ins2Index;
        ins2Index++;
        index++;
        for (int i = 0; i < len; i++) {
            ins2[ins2Index][0] = ele;
            for (int j = 0; j < ins2[i].length - 1; j++) {
                ins2[ins2Index][j + 1] = ins2[i][j];
            }
            ins2Index++;
        }
        return test212(ins2, ins2Index, ins, index);
    }

    //组合排列的个数
    public static int test3(int num, int result) {
        if (num > 0) {
            result = 2 * result;
            num --;
        } else {
            return result - 1;
        }
        return test3(num, result);
    }

    //过滤掉不合理的组合
    public static void test4(int[][][] ins2, int money) {
        int index = 0;
        int result = 0;
        while (index < ins2.length) {
            int[][] ins21 = ins2[index];
            //金额不超过指定金额
            int needMoney = 0;
            for (int i = 0; i < ins21.length; i++) {
                needMoney += ins21[i][0];
            }
            if (needMoney > money) {
                // System.out.println(index);
                index++;
                continue;
            }
            boolean sts = false;
            //存在附件时，必须存在主件
            for (int i = 0; i < ins21.length; i++) {
                int q = ins21[i][2];
                if (q > 0) {
                    //是否存在附件对应的主件
                    for (int j = 0; j < ins21.length; j++) {
                        sts = q == ins21[j][3];
                        if (sts)break;
                    }
                    if (!sts)break;
                } else {
                    sts = true;
                }
            }
            if (!sts) {
                index++;
                continue;
            }
            //获取满意度
            int number = 0;
            for (int k = 0; k < ins21.length; k++) {
                number = number + (ins21[k][0] * ins21[k][1]);
            }
            // System.out.println(number);
            result = result < number ? number : result;
            index++;
        }
        System.out.println(result);
    }

}
